package com.zklh.leetcode.top100;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * 验证二叉搜索树算法实现
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/11/13 10:39
 */
public class Solution98 {

    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Integer.MIN_VALUE-1L, Integer.MAX_VALUE+1L);
    }

    public boolean isValidBST(TreeNode root, long leftLimit, long rightLimit) {
        return root.val > leftLimit && root.val < rightLimit
                && (root.left == null || isValidBST(root.left, leftLimit, root.val))
                && (root.right == null || isValidBST(root.right, root.val, rightLimit));
    }

    public static void main(String[] args) {
        Solution98 solution = new Solution98();

        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(3);
        root2.right.right = new TreeNode(6);
        System.out.println(solution.isValidBST(root));
        System.out.println(solution.isValidBST(root2));
    }
}
